package leetcode.editor.cn.q1_300.q200;
//现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 
//prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。 
//
// 
// 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。 
// 
//
// 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。 
//
// 
//
// 示例 1： 
//
// 
//输入：numCourses = 2, prerequisites = [[1,0]]
//输出：[0,1]
//解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
// 
//
// 示例 2： 
//
// 
//输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
//输出：[0,2,1,3]
//解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
//因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。 
//
// 示例 3： 
//
// 
//输入：numCourses = 1, prerequisites = []
//输出：[0]
// 
//
// 
//提示：
//
// 
// 1 <= numCourses <= 2000 
// 0 <= prerequisites.length <= numCourses * (numCourses - 1) 
// prerequisites[i].length == 2 
// 0 <= ai, bi < numCourses 
// ai != bi 
// 所有[ai, bi] 互不相同 
//

import leetcode.editor.cn.util.arr.ArrayUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.IntStream;

public class Q210_CourseScheduleIi {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public int[] findOrder(int numCourses, int[][] prerequisites) {
            if (prerequisites == null || prerequisites.length == 0) {
                return IntStream.range(0, numCourses).toArray();
            }
            // 保存所有的 index 对应的前提
            List<List<Integer>> preList = new ArrayList<>();
            // 保存所有的 index 对应的后续
            List<List<Integer>> nextList = new ArrayList<>();
            for (int i = 0; i < numCourses; i++) {
                preList.add(new ArrayList<>());
                nextList.add(new ArrayList<>());
            }
            for (int i = 0; i < prerequisites.length; i++) {
                int next = prerequisites[i][0];
                int pre = prerequisites[i][1];

                preList.get(next).add(pre);
                nextList.get(pre).add(next);
            }
            List<Integer> noPreList = new ArrayList<>();
            // 获取到可以直接学习的课程
            for (int i = 0; i < preList.size(); i++) {
                if (preList.get(i).size() == 0) noPreList.add(i);
            }

            List<Integer> learned = new ArrayList<>();
            learned.addAll(noPreList);
            for (Integer i : noPreList) {
                if (learn(preList, nextList, i, learned, numCourses)) {
                    return learned.stream().mapToInt(Integer::intValue).toArray();
                }
            }

            return new int[]{};
        }

        private boolean learn(List<List<Integer>> preList, List<List<Integer>> nextList, int pre, List<Integer> learned, int size) {
            if (size == learned.size()) return true;

            for (Integer next : nextList.get(pre)) {
                if (learned.containsAll(preList.get(next))) {
                    if (!learned.contains(next)) {
                        learned.add(next);
                    }
                    if (learn(preList, nextList, next, learned, size)) {
                        return true;
                    }
                }
            }
            return false;
        }

    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q210_CourseScheduleIi().new Solution();
        // TO TEST
        int[][] ints = (int[][]) ArrayUtil.genArrayByString("[[5,6],[0,2],[1,7],[5,9],[1,8],[3,4],[0,6],[0,7],[0,3],[8,9]]");
        int[] order = solution.findOrder(10, ints);
        System.out.println(Arrays.toString(order));
    }
}